package com.learn.acm.two;

import org.junit.jupiter.api.Test;

/**
 *
 *
 * @author zhongshitao
 * @date 2020/12/23 3:36 下午
 */
public class Solution240 {


    public boolean searchMatrix(int[][] matrix, int target) {
        if (null == matrix || matrix.length <= 0) {
            return false;
        }
        int left = matrix[0].length - 1, up = 0;
        while (up < matrix.length && left >= 0) {
            if (target == matrix[up][left]) {
                return true;
            }
            if (target < matrix[up][left]) {
                left--;
            } else {
                up++;
            }
        }
        return false;
    }

    /**
     * 深度遍历
     * @param x
     * @param y
     * @param matrix
     * @param target
     * @return
     */
    private boolean isPattern(int x, int y, int[][] matrix, int target) {
        if (x >= matrix.length || y >= matrix[0].length) {
            return false;
        }
        if (target ==  matrix[x][y]) {
            return true;
        }

        if (isPattern(x+1,y,matrix,target)) {
            return true;
        }
        if (isPattern(x, y+1, matrix, target)) {
            return true;
        }
        if (isPattern(x+1, y+1, matrix, target)) {
            return true;
        }
        return false;
    }



    private boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
        int lo = start;
        int hi = vertical ? matrix[0].length-1 : matrix.length-1;

        while (hi >= lo) {
            int mid = (lo + hi)/2;
            if (vertical) { // searching a column
                if (matrix[start][mid] < target) {
                    lo = mid + 1;
                } else if (matrix[start][mid] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            } else { // searching a row
                if (matrix[mid][start] < target) {
                    lo = mid + 1;
                } else if (matrix[mid][start] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            }
        }

        return false;
    }

    public boolean searchMatrixForMid(int[][] matrix, int target) {
        // an empty matrix obviously does not contain `target`
        if (matrix == null || matrix.length == 0) {
            return false;
        }

        // iterate over matrix diagonals
        int shorterDim = Math.min(matrix.length, matrix[0].length);
        for (int i = 0; i < shorterDim; i++) {
            boolean verticalFound = binarySearch(matrix, target, i, true);
            boolean horizontalFound = binarySearch(matrix, target, i, false);
            if (verticalFound || horizontalFound) {
                return true;
            }
        }

        return false;
    }

    @Test
    public void test() {
        int[][] matrix = new int[][]{
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18,21,23,26,30}};
        int[][] matrix2 = new int[][]{{1,1}};
        System.out.println(searchMatrix(matrix,16));
    }





}
